//
// Created by yangchao on 2022/6/2.
// 116. 填充每个节点的下一个右侧节点指针: https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
//

#include "../DataStructure/Node.h"
#include <queue>
using namespace std;

class Connect {
public:
    //怎么判断同一层的右侧节点？
    Node* connect(Node* root) {
        if (root == nullptr) return root;
        //初始化队列同时将第一层节点加入队列中，即根节点
        queue<Node*> qu;
        qu.push(root);
        while (!qu.empty()) {
            int len = qu.size();
            //遍历这一层的所有节点
            for (int i = 0; i < len; ++i) {
                Node* node = qu.front();
                qu.pop();
                if (i < len-1) {
                    node->next = qu.front();
                }
                if (node->left != nullptr) qu.push(node->left);
                if (node->right != nullptr) qu.push(node->right);
            }
        }
        return root;
    }
};

